package arithmetic1.sort;

/*
    堆排序:
        1.将待排序列构建成一个大顶堆
        2.此时整个序列的最大值就是堆顶的根节点
        3.将其与末尾的元素进行交换。此时末尾就成为最大值
        4.然后将剩余的n-1个元素重新构造成一个大顶堆，这样会得到n-1个元素的最大值，如此返回执行，就能得到一个有序序列
 */
public class HeapSort {
    public static void main(String[] args) {
//        int arr[]={4,6,8,5,9,10,7,1,7,12,13};
        //创建一个非常大的随机数组
//        int arr[]=new int[100000];
//        for (int i = 0; i < arr.length; i++) {
//            arr[i]=(int)(Math.random()*1000000);
//        }

//        Date date=new Date();
//        SimpleDateFormat sdf=new SimpleDateFormat("yyyy-MM-dd hh:mm:ss");
//        String time1=sdf.format(date);
//        System.out.println("排序前时间为:"+time1);

        //堆排序
//        heapSort(arr);

//        date=new Date();
//        String time2=sdf.format(date);
//        System.out.println("排序后时间为:"+time2);

//        System.out.println(Arrays.toString(arr));
        System.out.println(power(2,17));
    }

    //堆排序
    public static void heapSort(int arr[],int start,int end){
        int temp;
        //重复进行数组长度-1次循环
        for(int i=0;i<arr.length-1;i++){
            //将数组构建成大顶堆
            broadHeap(arr,start,end);
            //将根节点与数组末尾节点交换
            temp=arr[end];
            arr[end]=arr[0];
            arr[0]=temp;
            //将最后一个元素排除在外再重复相同的操作
            end--;
        }
    }
    public static void heapSort(int arr[]){
        heapSort(arr,0,arr.length-1);
    }

    //将数组构建成大顶堆
    public static void broadHeap(int arr[],int start,int end){
        //计算二叉树的层数,层数=log(节点数+1)向上取整
        int lay=0;
        while (power(2,lay)-1<(end-start+1)){
            lay++;
        }
        //循环次数等于二叉树的层数-1
        for (int j = 0; j < lay-1; j++) {
            //从最后一个非叶子节点开始调整(最后一个非叶子节点索引:arr.length/2-1)
            for(int i=(end-start+1)/2-1;i>=start;i--){
                if((2*i+2)<=end){   //当前节点有右子节点
                    if(!(arr[i]>=arr[2*i+1] && arr[i]>=arr[2*i+2])){   //当前节点小于两个子节点中的其中一个
                        //将当前节点与两个子节点中大的那个交换
                        //定义一个中间变量
                        int temp;
                        if(arr[2*i+1]>arr[2*i+2]){  //左子节点大于右子节点
                            //将当前节点与左子节点交换
                            temp=arr[i];
                            arr[i]=arr[2*i+1];
                            arr[2*i+1]=temp;
                        }else {     //右子节点大于左子节点
                            //将当前节点与右子节点交换
                            temp=arr[i];
                            arr[i]=arr[2*i+2];
                            arr[2*i+2]=temp;
                        }
                    }
                }else {     //当前节点没有右子节点
                    if(arr[i]<arr[2*i+1]){  //当前节点小于左子节点
                        //将其交换
                        int temp=arr[i];
                        arr[i]=arr[2*i+1];
                        arr[2*i+1]=temp;
                    }
                }
            }
        }
    }

    //计算一个数的n次方
    public static int power(int x,int n){
        int result=x;
        for(int i=0;i<n-1;i++){
            result*=x;
        }
        return result;
    }
}
